use data_structure::prelude::*;

const CACHE_SIZE: usize = 1000;
const RANGE_SIZE: usize = 4;

fn ackermann(cache: &mut [[u64; CACHE_SIZE]; RANGE_SIZE], m: u64, n: u64) -> u64 {
    let mut stk_m: Stack<List<u64>> = Stack::new();
    let mut val = n;
    stk_m.push(m);

    while let Some(m) = stk_m.pop() {
        let in_cache = m < CACHE_SIZE as u64 && n < RANGE_SIZE as u64;
        if in_cache && cache[m as usize][val as usize] > 0 {
            val = cache[m as usize][val as usize];
        } else {
            match (m, val) {
                (0, _) => val += 1,
                (m, 0) => {
                    stk_m.push(m - 1);
                    val = 1;
                }
                (m, _) => {
                    stk_m.push(m - 1);
                    stk_m.push(m);
                    val -= 1;
                }
            }
        }
    }
    val
}

#[test]
fn solve_ackermann() {
    let mut cache = [[0u64; CACHE_SIZE]; RANGE_SIZE];
    // m == 0, 1, 2
    for m in 0..3 {
        for n in 0..CACHE_SIZE {
            cache[m][n] = ackermann(&mut cache, m as u64, n as u64);
        }
    }
    // m == 3
    for n in 0..60 {
        cache[3][n] = ackermann(&mut cache, 3, n as u64);
    }

    println!("{}", ackermann(&mut cache, 4, 5));
}
